#include "Queue.h"

void QueueInit(Queue *q)
{
    assert(q);
    q->qt = NULL;
    q->head = 0;
    q->tail = 0;
    q->Capacity = 0;
}

void QueueDestory(Queue *q)
{
    assert(q);
    free(q->qt);
    q->qt = NULL;
}

void QueuePush(Queue *q, QTDataType x)
{
    assert(q);
    if (q->Capacity == q->tail)
    {
        int newCapacity = q->Capacity == 0 ? 4 : q->Capacity * 2;
        QTDataType *p = (QTDataType *)malloc(sizeof(Queue) * newCapacity);
        if (p == NULL)
        {
            printf("malloc fail!!!\n");
            exit(EXIT_FAILURE);
        }
        q->qt = p;
    }

    q->qt[q->tail] = x;
    ++q->tail;
}

void QueuePop(Queue *q)
{
    assert(q);

    if (q->tail > 0)
    {
        int begin = 0;
        int end = q->tail - 1;
        while (end--)
        {
            q->qt[begin] = q->qt[begin + 1];
            ++begin;
        }
        --q->tail;
    }
}

bool QueueEmpty(Queue *q)
{
    assert(q);
    return q->head == 0 && q->tail == 0;
}

int QueueHead(Queue *q)
{
    assert(q);
    return q->qt[q->head];
}

int QueueTail(Queue *q)
{
    assert(q);
    return q->qt[q->tail - 1];
}

int main()
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    while (!QueueEmpty(&q))
    {
        printf("%d ", QueueHead(&q));
        QueuePop(&q);
    }
    printf("\n");
    system("pause");
    return 0;
}
